class Solution {
    vector<vector<string>> ret;
    vector<string> path;
    int _n;
    bool checkCol[10], checkDig1[20], checkDig2[20];

public:
    vector<vector<string>> solveNQueens(int n) {
        _n = n;
        path.resize(n);
        for(int i = 0; i < n; i++)
        {
            path[i].append(n, '.');
        }
        dfs(0);
        return ret;
    }

    void dfs(int row)
    {
        if(row == _n)
        {
            ret.push_back(path);
            return;
        }
        for(int col = 0; col < _n; ++col) // 枚举每一列，尝试在这⼀⾏放皇后
        {
            if(!checkCol[col] && !checkDig1[row - col + _n] && !checkDig2[row + col])
            {
                path[row][col] = 'Q';
                checkCol[col] = checkDig1[row - col + _n] = checkDig2[row + col] = true;
                dfs(row + 1);
                path[row][col] = '.'; // 恢复现场
                checkCol[col] = checkDig1[row - col + _n] = checkDig2[row + col] = false;
            }
        }
    }
};